Video applications are widely used recently and thus image and video compression techniques become an important issue of the modern telecommunication and storage mediums. More and more consumer electronic products, such as video telephone, video conference, HDTV and video on demand (VOD), need data compression techniques to reduce the transmission and storage data volume so as to meet the I/O bandwidth and obtain higher quality. Currently video compression standards, such as H.263, MPEG-1 and MPEG-2, all adopt motion estimation as part of the compression steps thereof. As the data volume is increased, a quick and efficient motion estimation hardware is needed to improve the performance of the video compression technique and reduce the temporal redundancy within frame sequences. Especially when the data volume of HDTV is more and more increased, a high performance and high computation motion estimator is needed to meet such a requirement.
Block matching algorithm is widely adopted in motion estimation. Full search algorithm can preferably find the exactly position of the block and obtain a superior video quality. However, it requires a large amount of computation and time. Therefore, fast search algorithms are developed to remove the drawbacks, such as extremely high computational complexity, of the full search algorithm. Among all the fast search algorithms, the 3-step hierarchical search block matching algorithm (3SHS) is considered as one of the best algorithms. Though the image quality obtained by the fast search algorithm is inferior to that of the full search algorithm, the amount of the computation is significantly reduced to 1/10.
Most of the conventional motion estimators focus on the hardware design of the full search algorithm because of its regular data flow, low control overhead and control complexity. Besides, currently hardware design of the 3-step search algorithm does not efficiently consider its irregular data flow and access characteristics of the memory. Therefore, the latency, bandwidth and cost are not satisfactory.